# Python 2.6.4
# Project Euler, Problem 31r
# Copyright 2010 Talha Zaman

from mine import timed, memoized

coins = [200,100,50,20,10,5,2,1]
@memoized
def ways(left,coin):
    if left==0: return 0
    if left==1: return 1
    total = 0
    for i in range(coin, 8):
        if left-coins[i]==0: total += 1
        elif left-coins[i]>0: total += ways(left-coins[i], i)
    return total

@timed
def run():
    return ways(200, 0)

print run()
